package cn.yuemouren.leetcode;

/**
 * @Author: Timi
 * @Description: 剑指offer练习题
 * @Date: 2020/8/18 15:45
 */
public class Test_x {

    public static void main(String[] args) {

    }

    /**
     * 括号匹配深度
     * @param s
     * @return
     */
    public int kuoHaoShenDu(String s){
        char[] ch = s.toCharArray();
        int max = 0,cnt = 0;
        for (int i = 0; i < ch.length; i++){
            if('(' == ch[i]){
                cnt++;
            } else {
                cnt--;
            }
            max = Math.max(max,cnt);
        }
        return max;
    }

    /**
     * 将字符串转换成数字
     *   如果是0 则是0，不是数字变成零
     * @param str
     * @return
     */
    public int strChangeNumber(String str){
        int length = str.length();
        if(length == 0)
            return 0;
        char[] ch = str.toCharArray();
        //判断是否存在符号位
        char f = ch[0];
        int flag = 0;
        if('+' == f){
            flag = 1;
        } else if('-' == f){
            flag = 2;
        }
        int start = flag > 0 ? 1 : 0;
        int res = 0;
        for(int i = start; i < length; i++){
            if(Character.isDefined(ch[i])){
                int j = ch[i] - '0';
                res = res * 10 + j;
            } else {
                return 0;
            }
        }
        return flag == 1 ? res : -res;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    /**
     * 翻转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head){

        ListNode next = null;
        ListNode pred = null;
        while(head != null){
            next = head.next;
            head.next = pred;
            pred = head;
            head = next;
        }
        return pred;
    }

    /**
     * 链表中倒数第k个元素
     * @param head
     * @param k
     * @return
     */
    public ListNode findKthToTail(ListNode head,int k){

        if(null == head || k <= 0){
            return null;
        }
        int index = k;//用于判断k值是否超过链表长度
        int count = 0;//链表长度
        ListNode node1 = head;
        ListNode node2 = head;
        while(node1 != null){
            node1 = node1.next;
            count++;
            if(k < 1){
                node2 = node2.next;
            }
            k--;
        }
        if(index > count){
            return null;
        }
        return node2;
    }

    /**
     * 合并两个链表，按照从小到大的顺序排列,利用递归实现
     * @param node1
     * @param node2
     * @return
     */
    public ListNode mergeListNode(ListNode node1,ListNode node2){
        //特殊情况
        if(null == node1)
            return node2;
        if(null == node2)
            return node1;

        //判断两个链表当前节点的值谁比较小
        if(node1.val < node2.val){
            node1.next = mergeListNode(node1.next,node2);
            return node1;
        } else{
            node2.next = mergeListNode(node1,node2.next);
            return node2;
        }
    }

    /**
     * 菲波那切数列 实现（递归，n值太大容易栈溢出）
     * @param n
     * @return
     */
    public int fibonacci1(int n){
        if(n <= 0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        return fibonacci1(n - 2) + fibonacci1(n - 1);
    }

    /**
     * 菲波那切数列 实现（利用迭代实现）
     * @param n
     * @return
     */
    public int fibonacci2(int n){
        if(n <= 0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        int first = 1,second = 1,third = 0;
        for (int i = 3; i < n; i++){
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }

    /**
     * 小青蛙跳台阶问题（利用迭代实现）
     *  可以有几种跳法
     * @param n
     * @return
     */
    public int jumpNumber(int n){
        if(n <= 0)
            return 0;
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
        int first = 1,second = 2,third = 0;
        for (int i = 3; i < n; i++){
            third = second + first;
            first = second;
            second = third;
        }
        return third;
    }

    /**
     * 小青蛙变态跳台阶问题（利用位运算实现，性能更高，执行时间更短）
     *  可以有几种跳法
     *   每次可挑 1-n级
     * @param n
     * @return
     */
    public int jumpBianNumber(int n){
        return 1 << --n;
    }
}
